K-th smallest in lexicographical order

Time: O(LogN); Space: O(LogN); hard

Given integers n and k, find the lexicographically k-th smallest integer in the range from 1 to n.

Constraints:

  • 1 ≤ k ≤ n ≤ 109

Example 1:

Input: n=13, k=2

Output: 10

Explanation:

  • The lexicographical order is [1, 10, 11, 12, 13, 2, 3, 4, 5, 6, 7, 8, 9], so the second smallest number is 10.

Example 2:

Input：n=200, k=18

Output：114

Explanation

  • 1,10,100,101,102,103,104,105,106,107,108,109,11,110,111,112,113,114，the eighteenth is 114.

[1]:

class Solution1(object):
    """
    Time: O(LogN)
    Space: O(LogN)
    """
    def findKthNumber(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: int
        """
        result = 0

        cnts = [0] * 10
        for i in range(1, 10):
            cnts[i] = cnts[i - 1] * 10 + 1

        nums = []
        i = n
        while i:
            nums.append(i % 10)
            i //= 10

        total, target = n, 0
        i = len(nums) - 1
        while i >= 0 and k > 0:

            target = target*10 + nums[i]
            start = int(i == len(nums)-1)

            for j in range(start, 10):
                candidate = result*10 + j
                if candidate < target:
                    num = cnts[i+1]
                elif candidate > target:
                    num = cnts[i]
                else:
                    num = total - cnts[i + 1]*(j-start) - cnts[i]*(9-j)

                if k > num:
                    k -= num
                else:
                    result = candidate
                    k -= 1
                    total = num-1
                    break
            i -= 1

        return result

[2]:

s = Solution1()

n = 13
k = 2
assert s.findKthNumber(n, k) == 10

n=200
k=18
assert s.findKthNumber(n, k) == 114

2.

[3]:

class Solution2(object):
    def findKthNumber(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: int
        """
        def count(n, prefix):
            result, number = 0, 1
            while prefix <= n:
                result += number
                prefix *= 10
                number *= 10
            result -= max(number//10 - (n - prefix//10 + 1), 0)
            return result

        def findKthNumberHelper(n, k, cur, index):
            if cur:
                index += 1
                if index == k:
                    return (cur, index)

            i = int(cur == 0)
            while i <= 9:
                cur = cur * 10 + i
                cnt = count(n, cur)
                if k > cnt + index:
                    index += cnt
                elif cur <= n:
                    result = findKthNumberHelper(n, k, cur, index)
                    if result[0]:
                        return result
                i += 1
                cur //= 10
            return (0, index)

        return findKthNumberHelper(n, k, 0, 0)[0]

[4]:

s = Solution2()

n = 13
k = 2
assert s.findKthNumber(n, k) == 10

n=200
k=18
assert s.findKthNumber(n, k) == 114